#include "primkruskal.h"
#include "pqueue.h"
#include "genlib.h"

bool isAUnion(edgeT edge, int *nodeId);

void prim(int **graph, int size){
	edgeT edge;
	bool *nodes;
	int currentNode = 0, i, freeNodes = size-1, total = 0;
	pqueueADT queue = NewPQueue();

	nodes=NewArray(size, bool);

	for(i = 0; i < size; i++){
		nodes[i] = 0;
	}

	//Insert first node into MST
	nodes[0] = 1;
	freeNodes--;

	while(TRUE){
		for(i = 0; i <= size-1; i++){
			if(graph[currentNode][i] != 0){
				edge.v1 = currentNode;
				edge.v2 = i;
				edge.value = graph[currentNode][i];

				Enqueue(queue,edge);
			}
		}

		do {
			edge=DequeueMin(queue);
		} while(nodes[edge.v2]);

		printf("(%d->%d) = %d\n", edge.v1, edge.v2, edge.value);
		total += edge.value;
		nodes[edge.v2] = 1;

		currentNode = edge.v2; 

		if(freeNodes == 0) break;
		freeNodes--;
	}
	printf("Size of MST: %d\n\n",total);
}

void kruskal(int **graph, int size){
	int i, j, *nodeId, nextId = 1, temp, total = 0;
	edgeT edge;
	pqueueADT queue = NewPQueue();
	nodeId = NewArray(size, int);

	for(i = 0; i < size; i++){
		for(j = 0; j < size; j++){
			if(graph[i][j] != 0 && graph[i][j] != 999){
				edge.value = graph[i][j];
				edge.v1 = i;
				edge.v2 = j;
				Enqueue(queue, edge);
			}
		}
	}

	//Init nodeId-array
	for(i = 0; i < size; i++)
		nodeId[i] = 0;

	//First tree.
	edge = DequeueMin(queue);
	nodeId[edge.v1] = nextId;
	nodeId[edge.v2] = nextId;
	nextId++;
	total += edge.value;
	printf("(%d, %d) = %d\n", edge.v1, edge.v2, edge.value);

	//All the other trees.
	while(!IsEmpty(queue)){

		edge = DequeueMin(queue);
		if(!isAUnion(edge, nodeId)){
			if(nodeId[edge.v1] == 0 && nodeId[edge.v2] == 0){		//New tree
				nodeId[edge.v1] = nextId;
				nodeId[edge.v2] = nextId;
				nextId++;
			}
			else if(nodeId[edge.v1] != 0 && nodeId[edge.v2] != 0){	//Merge tree
				temp = nodeId[edge.v2];
				for(i = 0; i < size; i++){
					if(nodeId[i] == temp){
						nodeId[i] = nodeId[edge.v1];
					}
				}
			}
			else if(nodeId[edge.v1] == 0 && nodeId[edge.v2] != 0){	//Single node
				nodeId[edge.v1] = nodeId[edge.v2];
			}
			else if(nodeId[edge.v2] == 0 && nodeId[edge.v1] != 0){
				nodeId[edge.v2] = nodeId[edge.v1];
			}
			
			printf("(%d, %d) = %d\n", edge.v1, edge.v2, edge.value);
			total += edge.value;
		}
	}
	printf("Size of MST: %d\n\n",total);
}

bool isAUnion(edgeT edge, int nodeId[]){
	if(nodeId[edge.v1] == nodeId[edge.v2] && nodeId[edge.v1] > 0)
		return TRUE;
	else
		return FALSE;
}